// CoreCalc, a spreadsheet core implementation 

// ----------------------------------------------------------------------
// Copyright (c) 2006-2009 Peter Sestoft and others

// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use, copy,
// modify, merge, publish, distribute, sublicense, and/or sell copies
// of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:

//  * The above copyright notice and this permission notice shall be
//    included in all copies or substantial portions of the Software.

//  * The software is provided "as is", without warranty of any kind,
//    express or implied, including but not limited to the warranties of
//    merchantability, fitness for a particular purpose and
//    noninfringement.  In no event shall the authors or copyright
//    holders be liable for any claim, damages or other liability,
//    whether in an action of contract, tort or otherwise, arising from,
//    out of or in connection with the software or the use or other
//    dealings in the software.
// ----------------------------------------------------------------------

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using C5;
using System.Reflection.Emit;
using System.Reflection;

namespace CoreCalc.SheetDefinedFunctions
{
  /// <summary>
  /// Converts the topological list of cell addresses to a list of CGExpr and also
  /// compiles it
  /// </summary>
  class TopoListToCGExprList
  {
    private readonly Dictionary<FullCellAddr, Variable> addressToVariable;
    private readonly HashedLinkedList<FullCellAddr> cellList;
    private readonly FullCellAddr[] inputCells;

    public TopoListToCGExprList(HashedLinkedList<FullCellAddr> cellList, FullCellAddr[] inputCells)
    {
      addressToVariable = new Dictionary<FullCellAddr, Variable>();
      this.cellList = cellList;
      this.inputCells = inputCells;
    }

    public Delegate CreateSdfDelegate(DependencyGraph dpGraph)
    {
      int arity = dpGraph.inputCells.Length;
      // Create dynamic method with signature: Value CGMethod(Value, Value, ...) in class Function:
      DynamicMethod method = new DynamicMethod("CGMethod", Value.type, SdfInfo.argumentTypes[arity], 
                                               Function.type, true);
      ILGenerator ilg = method.GetILGenerator();
      CodeGenerate.Initialize(ilg); 
      SetVariablesFromInput(ilg);
      ProcessList(dpGraph);
      ilg.Emit(OpCodes.Ret);
      return method.CreateDelegate(SdfInfo.sdfDelegateType[arity]);
    }

    private void ProcessList(DependencyGraph dpGraph)
    {
      // Set the mapping from cell addresses to local variables 
      // for use by CGExpr subclass objects -- perhaps should be 
      // in CodeGenerate from the outset
      CodeGenerate.SetVariables(addressToVariable);
      ProgramLines program = ConvertExprToCGExpr(dpGraph);
      if (SdfManager.MarkLevel != MarkLevel.MarkIV)
      {
        program.CreateUnwrappedValuesOfStrictCells();
        program.Compile();
      }
      else
      {
        program.ComputeEvalConds(dpGraph);
        // Re-sort the expressions to reflect new dependencies 
        // introduced by evaluation conditions
        DependencyGraph augmentedGraph
          = new DependencyGraph(dpGraph.outputCell, dpGraph.inputCells,
              delegate(FullCellAddr fca) { return (IDepend)(program.GetProgramListNode(fca)); });
        augmentedGraph.CollectPrecedents();
        TopologicalSorter sorter = new TopologicalSorter(augmentedGraph);
        HashedLinkedList<FullCellAddr> augmentedList = sorter.Toposort(dpGraph.outputCell);
        ProgramLines finalProgram = new ProgramLines();
        foreach (FullCellAddr cellAddr in augmentedList)
        {
          ICompilable icomp = program.GetProgramListNode(cellAddr);
          if (icomp != null)
            finalProgram.AddLineForCell(cellAddr, icomp);
          else
            Console.WriteLine("Null at {0}", cellAddr);
        }
        // This relies on all pathconds having been generated at this point
        CGCachedExpr.EmitCacheInitializations();
        finalProgram.CreateUnwrappedValuesOfStrictCells();
        finalProgram.Compile();
      } 
    }

    /// <summary>
    /// Compiles the topologically sorted list of Expr to a list (program) 
    /// of CGExprs.  Builds a map from cellAddr to local variable ids, 
    /// for compiling sheet-internal cellrefs to ldloc instructions.  
    /// </summary>
    private ProgramLines ConvertExprToCGExpr(DependencyGraph dpGraph)
    {
      ProgramLines program = new ProgramLines();
      foreach (FullCellAddr cellAddr in this.cellList)
      {
        if (!cellList.Last.Equals(cellAddr))
        {
          HashSet<FullCellAddr> dependents = dpGraph.GetDependents(cellAddr);
          int minUses = dependents.Count;
          if (dependents.Count == 1)
          {
            FullCellAddr fromFca = dependents.Choose();
            minUses = Math.Max(minUses, GetCount(fromFca, cellAddr));
          }
          // Now if minUses==1 then there is at most one use of the cell at cellAddr,
          // and no local variable is needed.  Otherwise, allocate a local variable:
          if (minUses > 1)
          {
            // Console.WriteLine("Compiling cell {0} to variable", cellAddr);
            CGExpr newExpr = CGExpressionBuilder.BuildExpression(cellAddr, addressToVariable);
            Variable var = new LocalVariable(CodeGenerate.ilg, cellAddr.ToString(), newExpr.Type());
            program.AddLineForCell(cellAddr, new ComputeAndSetVariable(newExpr, var, cellAddr));
            addressToVariable.Add(cellAddr, var);
          }
        }
        else
        {
          // Special case for the last (that is, return value) expression          
          CGExpr outputExpr = CGExpressionBuilder.BuildExpression(cellAddr, addressToVariable);
          outputExpr.NoteTailPosition();
          program.AddLineForCell(cellAddr, outputExpr);
          // program.AddLine(outputExpr);
        }
      }
      return program;
    }

    /// <summary>
    /// Count number of references from cell at fromFca to cell address toFca
    /// </summary>
    private static int GetCount(FullCellAddr fromFca, FullCellAddr toFca)
    {
      int count = 0;
      Cell fromCell;
      if (fromFca.TryGetCell(out fromCell))
        fromCell.DependsOn(fromFca,
          delegate(FullCellAddr fca) { if (toFca.Equals(fca)) count++; });
      return count;
    }

    /// <summary>
    /// Generate code to load each input array element into 
    /// a local variable of type Value.  One might optimize this
    /// to avoid allocating a local variable if it is not used.
    /// But should not optimize to load lazily, because the same 
    /// input value array may be reused in recursive calls!
    /// </summary>
    /// <param name="ilg"></param>
    private void SetVariablesFromInput(ILGenerator ilg)
    {
      int arity = inputCells.Length;
      for (int i = 0; i < inputCells.Length; i++)
      {
        FullCellAddr addr = inputCells[i];
        cellList.Remove(addr);

        Variable var = new LocalArgument(addr.ToString(), Typ.Value, i);
        addressToVariable.Add(addr, var);
      }
    }
  }

  // --------------------------------------------------------------------------

  /// <summary>
  /// Expression visitor that builds a CGExpr by traversing the given expression
  /// </summary>
  class CGExpressionBuilder : IExpressionVisitor
  {
    private readonly Dictionary<FullCellAddr, Variable> addressToVariable;
    private FullCellAddr thisFca; // The cell containing the Expr being translated
    private CGExpr result;        // The result of the compilation is left here

    private CGExpressionBuilder(Dictionary<FullCellAddr, Variable> addressToVariable, FullCellAddr addr)
    {
      thisFca = addr;
      this.addressToVariable = addressToVariable;
    }

    public static CGExpr BuildExpression(FullCellAddr addr,
      Dictionary<FullCellAddr, Variable> addressToVariable)
    {
      Cell cell;
      if (!addr.TryGetCell(out cell))
        return new CGTextConst(TextValue.EMPTY);
      else if (cell is NumberCell)
        return new CGNumberConst(((NumberCell)cell).value);
      else if (cell is TextCell)
        return new CGTextConst(((TextCell)cell).value);
      else if (cell is QuoteCell)
        return new CGTextConst(((QuoteCell)cell).value);
      else if (cell is Formula)
      {
        // Translate the expr relative to its containing cell at addr
        CGExpressionBuilder cgBuilder = new CGExpressionBuilder(addressToVariable, addr);
        Expr expr = ((Formula)cell).Expr;
        expr.VisitorCall(cgBuilder);
        return cgBuilder.result;
      }
      else if (cell is ArrayFormula)
        return new CGError("Array formula in function sheet");
      else
        throw new ImpossibleException("BuildExpression: " + cell);
    }

    public void CallVisitor(CellArea cellArea)
    {
      result = new CGNormalCellArea(cellArea.ArrayView(thisFca));
    }

    public void CallVisitor(CellRef cellRef)
    {
      FullCellAddr cellAddr = cellRef.GetAbsoluteAddr(thisFca);
      if (cellAddr.sheet != thisFca.sheet) 
        // Reference to other sheet, hopefully a normal sheet
        result = new CGNormalCellRef(cellAddr);
      else if (this.addressToVariable.ContainsKey(cellAddr))
        // Reference to a cell that has already been computed in a local variable
        result = new CGCellRef(cellAddr);
      else // Inline the cell's formula's expression
        result = BuildExpression(cellAddr, addressToVariable);
    }

    public void CallVisitor(FunCall funCall)
    {
      CGExpr[] expressions = new CGExpr[funCall.es.Length];
      for (int i=0; i<funCall.es.Length; i++)
      {
        funCall.es[i].VisitorCall(this);
        expressions[i] = result;
      } 
      result = CGFunction.Make(funCall.function.name, expressions);
    }

    public void CallVisitor(Error error)
    {
      result = new CGError(error.ToString());
    }

    public void CallVisitor(NumberConst numbConst)
    {
      result = new CGNumberConst(numbConst.value);
    }

    public void CallVisitor(TextConst textConst)
    {
      result = new CGTextConst(textConst.value);
    }
  }
}